import Node from '../types/INode'

import {btPrint} from 'hy-algokit'

class TreeNode<T> extends Node<T> {
    left : TreeNode<T> | null = null;
    right : TreeNode<T> | null = null;
}

class BSTree<T> {
    private root: TreeNode<T> | null = null;

    print(){
        btPrint(this.root)
    }

    // 插入数据的操作
    insert(value:T){
        // 1、根据传入value创建Node(TreeNode)节点
        const newNode = new TreeNode<T>(value)

        // 2、判断当前是否有根节点
        if(!this.root){//当前树为空
            this.root = newNode;
        }else{// 树中已经有其他值
            this.insertNode(this.root,newNode)
        }
    }
    private insertNode(node: TreeNode<T>,newNode: TreeNode<T>){
        if(newNode.value < node.value){// 去左边继续查找空白位置
            if(node.left === null){// node节点的左边已经是空白
                node.left = newNode
            }else{
                this.insertNode(node.left,newNode)
            }
        }else{
            if(node.right === null){
                node.right = newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }
    }

    // 遍历的操作
    // 先序遍历
    preOrderTraverse(){
        this.preOrderTraverseNode(this.root)
    }
   private preOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            console.log(node.value)
            this.preOrderTraverseNode(node.left)
            this.preOrderTraverseNode(node.right)
        }
    }

    // 中序遍历
    inOrderTraverse(){
        this.inOrderTraverseNode(this.root)
    }
    private inOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            this.inOrderTraverseNode(node.left)
            console.log(node.value)
            this.inOrderTraverseNode(node.right)
        }
    }

    // 后序遍历
    postOrderTraverse(){
        this.postOrderTraverseNode(this.root)
    }
   private postOrderTraverseNode(node:TreeNode<T> | null){
        if(node){
            this.postOrderTraverseNode(node.left)
            this.postOrderTraverseNode(node.right)
            console.log(node.value)
        }
    }

    // 层序遍历(使用队列)
    levelOrderTraverse(){
        // 1、如果没有根节点，不需要遍历
        if(!this.root) return;
        // 2、创建队列
        const queue: TreeNode<T>[] = [];
        // 第一个节点是根节点
        queue.push(this.root);
        while(queue.length){
            // 3.1访问节点的过程,这里肯定是有数据的,素偶哦加个断言
            const current = queue.shift()!
            console.log(current.value)

            // 3.2 将左子节点放入到队列里面
            if(current.left){
                queue.push(current.left);
            }
            // 3.2 将右子节点放入到队列里面
            if(current.right){
                queue.push(current.right);
            }
        }
    }

    // 获取最值操作(最大值和最小值)
    getMaxValue(): T | null {
        let current = this.root;
        while(current && current.right){
            current = current.right;
        }
        return current?.value ?? null;
    }

    getMinValue(): T | null {
        let current = this.root;
        while(current && current.left){
            current = current.left;
        }
        return current?.value ?? null;
    }

    // 搜索特定的值：20 => boolean
    search(value:T):boolean {
        let current = this.root;
        while(current){
            // 如果搜索的数值和根节点相等
            if (current.value === value) return true
            // 比根节点大
            if (current.value < value){
                current = current.right;
            }else{
                current=current.left
            }
        }
        return false
    }
}

 const bst = new BSTree<number>()
 bst.insert(11)
 bst.insert(7)

 bst.insert(15)

 bst.insert(5)
 bst.insert(3)
 bst.insert(9)
 bst.insert(8)
 bst.insert(10)
 bst.insert(13)
 bst.insert(12)
 bst.insert(14)
 bst.insert(20)
 bst.insert(18)
 bst.insert(25)
 bst.insert(6)

//  bst.preOrderTraverse()
//  bst.inOrderTraverse()
//  bst.postOrderTraverse()
 
//  bst.levelOrderTraverse()

//  bst.print()
//  print(bst.root)

console.log(bst.getMaxValue())
console.log(bst.getMinValue())
console.log(bst.search(30))


export default {}